function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}



//使用类似与快慢指针的方式去做比较,将数组进行分区
function partition(arr, left ,right) {     // 分区操作
    var pivot = left,                      // 设定基准值（pivot）
        index = pivot + 1;
    for (var i = index; i <= right; i++) { //index为慢指针,i为快指针
        if (arr[i] < arr[pivot]) { //交换快慢慢指针
            swap(arr, i, index); 
            index++; //快慢指针都往前移动一步
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}


let arr = [8,4,6,2,8,3,9,2,5]
console.log(quickSort(arr,0,arr.length))